---
title: "forgery"
created: 2025-11-28
tags:
  - 算法
---

# forgery

## 题目 [Forgery](https://www.luogu.com.cn/problem/CF1059B)

![[image-beab646d.png]]

## 思路分析

其实和染色法没任何关系 一道枚举题

可以染色**无数次**，那么应该很容易想到，只要出现了一个点在目标图中是被 `#` 围成了一个圈的并且周围一圈都没有越界，那么就在当前图中染掉，然后去到下一个点。

全部染完之后与目标图比对一下就行了，一样就输出 `YES` ,反之则 `NO` 。

策略很简单，但是找到满足条件的点有两种方法：枚举或深搜。

枚举比dfs时空都要优些

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=1005;

char went[N][N],now[N][N];

int dx[8]={0,0,1,1,-1,-1,1,-1};

int dy[8]={1,-1,1,-1,1,-1,0,0};

int n,m;

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			cin>>went[i][j];

			now[i][j]='.';

		}

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			bool flag=false;

			for(int k=0;k<=7;k++){

				int nx=i+dx[k],ny=j+dy[k];

				if(nx<=0 || nx>n || ny<=0 || ny>m || went[nx][ny]=='.'){

					flag=true;

					break;

				}

			}

			if(flag)

				continue;

			for(int k=0;k<=7;k++){

				int nx=i+dx[k],ny=j+dy[k];

				now[nx][ny]='#';

			}

		}

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(went[i][j]!=now[i][j]){

				cout<<"NO"<<endl;

				return 0;

			}

		}

	}

	cout<<"YES"<<endl;

	return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=1005;

char went[N][N],now[N][N];

bool st[N][N];

int n,m;

int dx[8]={0,0,1,1,-1,-1,1,-1};

int dy[8]={1,-1,1,-1,1,-1,0,0};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m && !st[x][y];

}

void dfs(int x,int y){

	bool flag=false;

	for(int k=0;k<=7;k++){

		int nx=x+dx[k],ny=y+dy[k];

		if(nx<=0 || nx>n || ny<=0 || ny>m || went[nx][ny]=='.'){

			flag=true;

			break;

		}

	}

	for(int k=0;k<=7;k++){

		int nx=x+dx[k],ny=y+dy[k];

		if(!flag)

			now[nx][ny]='#';

		if(isVaild(nx,ny)){

			st[nx][ny]=true;

			dfs(nx,ny);

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			cin>>went[i][j];

			now[i][j]='.';

		}

	}

	dfs(1,1);

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			if(went[i][j]!=now[i][j]){

				cout<<"NO"<<endl;

				return 0;

			}

		}

	}

	cout<<"YES"<<endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[最小步数|最小步数]] 🏠 [[00-刷题理模型]] ➡️ [[填涂颜色|填涂颜色]]